There is increasing interest in the use of three-dimensional models of physical objects to improve productivity and innovation in fields such as digital imaging, computer animation, special effects in film, prototype imaging in product development, topography, reconstructive and plastic surgery, dentistry, architecture, industrial design, anthropology, milling and object production, biology, and internal medicine. In addition, with the recent explosion of the Internet and the World Wide Web, there is a demand for computer-generated 3D models for use on Web sites. Although 2D images currently predominate in the display and manipulation of graphic images on the World Wide Web, the use of 3D object models is a more efficient way to present graphic information for interactive graphics, animated special effects and other applications. The use of 3D models is growing in Web-based and other applications and continued growth is expected as personal computer systems become more powerful and bandwidth limitations are eliminated.
There are a number of ways of creating 3D models. Creating the model directly from the physical object itself is probably the most accurate and time efficient method. This can be accomplished in a number of ways. For example, a 3D model can be created using silhouette capture, as described in copending application entitled “System and Method of Three-Dimensional Image Capture and Modeling” filed concurrently with this application and assigned U.S. application Ser. No. 09/819,499, the whole of which is incorporated herein by reference. Laser scanning techniques may also be used to create 3D models from real-world objects. Alternatively, the 3D model may be constructed “by hand” on a computer by an artist who draws the model directly by placing vertices or faces or by combining smaller geometric shapes to form the overall model.
A 3D model is typically constructed using 3D spatial data and color or other data (called “texture data”) that is associated with specific areas of the model (such texture data is used to render displays or images of those portions of the model). Spatial data includes 3D X, Y, Z coordinates that describe the physical dimensions, contours and features of the object being modeled. This 3D point data usually defines a “wire-frame” model that describes the surface of the object being modeled and represents it as a series of interconnected planar shapes (sometimes called “geometric primitives” or “faces”), such as a mesh of triangles, quadrangles or more complex polygons. These wire frame models can be either gridded mesh models or irregular mesh models.
Gridded mesh models superimpose a grid structure as the basic framework for the model surface. The computer connects the grid points to form even-sized geometric shapes that fit within the overall grid structure. While gridded models provide regular, predictable structures, they are not well-suited for mesh constructions based on an irregular set of data points, such as those generated through laser scanning or silhouette capture of real world objects. The need to interpolate an irregular set of data points into a regular grid structure increases computation time and decreases the overall accuracy of the model. Gridded mesh models are more typically used when the model is constructed by hand.
More frequently, 3D models created from real-world objects use an irregular mesh model, such as an irregular triangulated mesh, to represent the real-world object more accurately. An irregular mesh model imposes no grid structure upon the model. Instead, the actual 3D X, Y, Z data points are used directly as the vertices in each planar shape or “face” of the mesh.
In addition to using spatial data, 3D object modeling systems also include texture data as a part of the object model. Texture data is color and pattern information that replicates an object's surface features. Some 3D object modeling systems maintain texture data separately from the “wire-frame” mesh data and apply the texture data to the mesh only when rendering the surface features. Those object modeling systems typically include two distinct and separate processes: first, in a mesh building phase, the system constructs a “wire frame” mesh to represent the object's spatial structure using only 3D X, Y, Z values (and other related spatial information) and, second, during a “texture map” building phase, the system assigns texture data to each of the faces of the mesh model, so that when the model is later rendered, the displaying device can overlay texture data on the geometric faces of the model. The rough face of a brick, the smooth and reflective surface of a mirror and the details of a product label can all be overlaid onto a mesh wire frame model using texture mapping techniques.
For models of real-world objects, texture data typically comes from 2D photographic images. The 3D spatial coordinate values of a mesh model face can be related and linked to specific points (i.e. two-dimensional x, y pixel locations) in the digitized versions of the collected photo images. Commercially available digital cameras output image frames, each of which includes a 2D matrix of pixels (e.g. 640×480 pixels in dimension), with each pixel having, for example, a three-byte (24 bit) red, green and blue (R, G, B) color assignment. Such a 3D object modeling system will then store each such photographic image as a “bitmap” (such as in TIFF format). The 3D object modeling system will link each mesh face in the generated 3D mesh model to a specific area in a selected bitmap that contains the appropriate texture data. When showing a view of the 3D model, a displaying device then clips relevant areas of the appropriate bitmap and overlays the clip on the associated mesh face.
Regardless of how the model is created, at least some manual adjustment of the model is usually necessary to attain the desired finished appearance. In the case of a model created by hand, the entire creation process is one of manual placement and adjustment of vertices, faces, and textures. Many users have difficulty making these adjustments because they require manipulating a three dimensional object (i.e. the mesh model) in what is essentially a two dimensional space (i.e. the computer screen) using tools that generally move in only two dimensions (i.e. the mouse and cursor keys). Other difficulties arise from the fact that mesh manipulation is limited to manipulating entire faces or vertices. For example, when a user wishes to change the appearance of a large flat area on the mesh that has only a few faces, additional faces and vertices must be added if any significant change is desired. Adding vertices and faces can be very difficult if it has to be done manually, especially for a novice user. Even those users who are proficient at these kinds of manipulation likely experienced a significant learning curve before becoming proficient. It would be useful to allow users more precision in manipulating mesh models as well as increasing ease of use.
Furthermore, most users find it useful to be able to manipulate the mesh in real time rather than make an adjustment to the model and then wait while the computer system renders the model. However, real time 3D rendering requires that the computer system perform a tremendous number of calculations in a short period of time. Users also frequently make changes to a mesh model, discard those changes as unwanted, and revert back to a prior version. This functionality is generally implemented by what is known as an “undo” operation. Implementing this operation usually requires that a copy of every previous version of the mesh model to be kept in memory. If the mesh model is of any significant size, the memory limitations of the computer may become taxed relatively quickly. It would be useful to be able to reduce the amount of real time calculations and memory requirements necessary to perform the 3D mesh manipulation.